class Trie:

    END_WORD = "#"

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = {}


    def insert(self, word: str):
        """
        Inserts a word into the trie.
        """
        if not word:
            return

        node = self.root
        for char in word:
            node = node.setdefault(char, {})
        node[Trie.END_WORD] = Trie.END_WORD



    def search(self, word: str):
        """
        Returns if the word is in the trie.
        """
        if not word:
            return False
        
        node = self.root
        for char in word:
            if char not in node: return False
            node = node[char]

        return Trie.END_WORD in node

    def startsWith(self, prefix: str):
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        if not prefix:
            return False

        node = self.root
        for char in prefix:
            if char not in node: return False
            node = node[char]

        return True

if __name__ == '__main__':
    trie = Trie()
    trie.insert("apple")
    print(trie.search("apple"))
    print(trie.search("app"))
    print(trie.startsWith("app"))
    trie.insert("app")
    print(trie.search("app"))

    